package com.pan.alg.niuke.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 描述
 * 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
 *
 * 数据范围：树上节点数满足 1 \le n \le 10^5 \1≤n≤10
 * 5
 *    , 节点值val满足区间 [0,n)
 * 要求：时间复杂度 O(n)O(n)
 *
 * 注：本题保证二叉树中每个节点的val值均不相同。
 *
 * 如当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：
 */
public class TreeLowestCommonAncestor2 {

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        List<Integer> path1 = new ArrayList<>();
        List<Integer> path2 = new ArrayList<>();
        getPath(root,o1,path1);
        hasVal =false;
        getPath(root,o2,path2);
        int result=0;
        for (int i = 0; i < path1.size()&&i<path2.size(); i++) {
            int v1 = path1.get(i);
            int v2 = path2.get(i);
            if(v1==v2){
                result=v1;
            }else {
                break;
            }
        }
        return result;

    }

    boolean hasVal =false;
    private void getPath(TreeNode root, int o1, List<Integer> path1) {
        if(root==null){
            return;
        }
        if(root.val==o1){
            hasVal=true;
            return;
        }

        path1.add(root.val);

        getPath(root.left,o1,path1);
        if(hasVal){
            return;
        }

        getPath(root.right,o1,path1);

        if(!hasVal){
            path1.remove(path1.size()-1);
        }
    }
}
